
\subsection{Grundlagen}
\subsubsection{Kleiner Satz von Fermat / Satz von Euler \buchmann{3.11}}
Wenn $ggT(a,m)=1$, dann gilt $$a^{\varphi(m)}\equiv1\mod{m}$$\label{euler}

\subsubsection{Schnelle Exponentation \buchmann{3.12}}
\textbf{Motivation:} Die Modifikation 
$$ a^{\varphi(m)-1}*a \equiv 1 \mod{m} $$
des Satzes \ref{euler} bietet eine Möglichkeit Restklassen zu invertieren, denn
$$ x \equiv a^{\varphi(m)-1} $$
liefert ein x für die Lösung der Kongruenz
$$ ax \equiv1 \mod{m} $$
was wiederum die Definition von inversen Elementen war. Bisher konnte das der erweiterte Euklidische Algorithmus lösen. Wenn diese Variante effizient sein soll, benötigt man eine \textit{schnelle Exponentation}, auch \textit{square-and-multiply}-Verfahren genannt.
\newline\newline
Es beruht darauf, dass 
\begin{enumerate}
\item eine Summe im Exponenten durch ein Produkt ersetzt werden kann
$$ g^e=g^{\sum_{i=0}^{n}e_i2^i}=\prod\limits_{i=0}^{k}{({g^2}^i)^e}^i=\prod\limits_{0\leq{i}\leq{k},e_i=1}{g^2}^i $$
\item sich die sukzessiven Quadrate eine Binärentwicklung aus dem vorherigen Element durch quadrieren bilden lassen
$$ {g^2}^{i}=({g^2}^{i-1})^2 $$
\item durch den Zahlenraum $\mathbb{Z}/m\mathbb{Z}$ bei der Berechnung die Ergebnisse kleiner $m$ bleiben.
\end{enumerate}
In Zahlen bedeutet das für $6^{73} \mod 100$:
\begin{itemize}
 \item $ 73=2^0+2^3+2^6 $
 \item $ 6^{73}\equiv6*{6^2}^3*{6^2}^6 $
 \item 
  \begin{itemize}
    \item $ {\bf{6^2}^0}=6 $
    \item $ {6^2}^1=6^2=36 $
    \item $ {6^2}^2=36^2 \equiv 96 \equiv -4 \mod100 $
    \item $ {\bf{6^2}^3}\equiv(-4)^2 \equiv 16 \mod 100 $
    \item $ {6^2}^4\equiv16^2 \equiv 56 \mod 100 $
    \item $ {6^2}^5\equiv 56^2 \equiv 36 \mod 100 $
    \item $ {\bf{6^2}^6}\equiv 36^2 \equiv -4 \mod 100 $
  \end{itemize}
 \item $ 6^{73}\equiv6*{6^2}^3*{6^2}^6\equiv6*16*(-4)\equiv-384\equiv16\mod100 $
\end{itemize}
\emph{Ein bisschen weniger mathematisch, dafür Informatikerverständlich heißt das:}

Man nehme den Exponenten $e$ in Binärdarstellung, also $73_d = 0100.1001_b$. Dann verrät mir jede $1_b$, welche 2er-Potenz verwendet wird, und somit welches Quadrat dieser Potenz(${g^2}^i$) ich für die Multiplikation verwenden muss.
  \begin{itemize}
    \item Wenn LSB von $e_b = 1$ (d.h. $e_d$ ungerade), \textit{result = result * aktuellePotenz} und betrachte nächstes Bit (\mbox{$e_d$/${2}$} oder rechtsshift von $e_b$)
    \item Wenn LSB von $e_b = 0$, shift
    \item Sobald $e_b = 0$ steht in \textit{result} das Ergebnis der aufmultiplizieren Potenz-Quadrate, auf englisch eben \textit{square-and-multiply}
  \end{itemize}


\subsection{Erzeugungsverfahren}
\subsubsection{Probedivision \buchmann{8.1}}
\textbf{Idee:} Man erzeugt eine zufällige Zahl $n$ der gewünschten Größe.
Nun muss man 'nur' prüfen, ob keine Primzahl $p$ unterhalb $\sqrt{n}$ die Zahl $n$ teilt.
'Nur' deshalb, weil der Aufwand mit der Anahl Primzahlen logarithmisch steigt.
Für hinreichend große $n$ gibt es $n/\log{n}$ Primzahlen (wird mit $\pi(n)$ bezeichnet) und man benötigt $\sqrt{n}/\log\sqrt{n}$ Probedivisionen.

Im folgenden Graphen ist:
  \begin{itemize}
    \item $f(x) = \pi(n)$, also die Anzahl Primzahlen
    \item $g(x)$ die benötigte Anzahl Probedivisionen
  \end{itemize}
Die Achsen sind logarithmisch aufgetragen, die dort aufgetragenen x und y wachsen also schon exponentiell
\begin{figure}[H]
\includegraphics[width=0.5\linewidth]{gfx/graph1.png}
%\caption{Aufwand von Probedivisionen}
\end{figure}
In der Praxis wird dieses Verfahren deshalb nur bis $n=10^6$ ($\pi(10^6) = 78498$) angewendet, was wie hier zu sehen $\sim$100 Probedivisionen bedeutet.

\subsubsection{Fermat-Test \buchmann{8.2}}
Der kleine Satz des Fermat kann direkt dazu benutzt werden, Zahlen auf Zusammengesetztheit zu prüfen. Wenn $n\in\mathbb{P}$, dann gilt für alle $a \in \Z$ mit $ggT(a,n)=1$
$$ a^{n-1} \equiv 1 \mod n $$
Im Gegenzug heißt das: Wenn man für ein beliebiges $n$ ein $a$ finden kann, für das die Kongruenz \emph{nicht} gilt, ist bewiesen dass $n$ zusammengesetzt ist.

Einschränkungen sind jedoch:
  \begin{itemize}
    \item Der Fermat-Test kann beweisen, dass $n$ zusammengesetzt ist, findet aber seine Teiler nicht
    \item ebenso gibt es besondere Zahlen, welche das 'Fermat-Merkmal' aufweisen (also sich zu einem $n$ ein $a$ findet, welches die Kongruenz erfüllt), aber $n$ trotzdem nicht prim ist. Der Rückschluss 'Wenn die Kongurenz gilt, ist $n$ prim' ist also nur bedingt gültig
  \end{itemize}
Der Fermat-Test dient somit in der Praxis nur als 'Negativ-Test' auf Nicht-Primalität. 
Ein Beispiel für besondere Zahlen, die diesen Test austricksen, sind die im folgenden beschriebenen Carmichael-Zahlen.

\subsubsection{Carmichael-Zahlen \buchmann{8.3}}
Eine Zahl $n$, die den Fermat-Test besteht, heißt \textit{Pseudoprimzahl zur basis a} wenn folgendes gilt:
\begin{itemize}
 \item $n$ ist ungerade
 \item $n$ ist zusammengesetzt
 \item Es gibt eine Basis $a$, die zusammen mit $n$ die Konruenz $ a^{n-1} \equiv 1 \mod n $ löst.
\end{itemize}
Gilt dies für alle $a \in \mathbb{Z}$ so heißt $n$ Carmichael-Zahl. Die kleinste solche Zahl ist $561=3*11*17$, es gibt jedoch unendlich viele.

\subsubsection{Miller-Rabin-Test \buchmann{8.3}}
Verschärft man den kleinen Satz des Fermat, erhält man ein Verfahren, welches mit hoher Wahrscheinlichkeit \textit{korrekt} vorhersagen kann, ob eine Zahl prim ist oder nicht.
Der Miller-Rabin-Test beruht auf 2 Kongruenzen, von denen mind. eine für die Primzahl $n$ gelten muss:
\begin{equation}
   a^d \equiv 1 \mod n
   \label{mr_bed1}
\end{equation}
\begin{equation}
   a^{{2^r}d} \equiv -1 \mod n
   \label{mr_bed2}
\end{equation}
$d$ ist ungerade und berechnet sich aus 
$$ d = \frac{n-1}{2^s} $$
mit $s$ als größte Potenz, welche $n-1$ teilt.
$$ s = max\lbrace r\in\mathbb{N} : 2^r \mid n-1 \rbrace $$
Nun machen wir uns an die Zeugenbefragung. Gesucht ist, wer sicher weiß, dass $n$ \textit{keine} Primzahl ist:
\begin{itemize}
 \item $a$ ist teilerfremd zu $n$
 \item $a$ erfüllt Kongruenz \ref{mr_bed1} nicht
 \item $a$ erfüllt Kongruenz \ref{mr_bed2} für alle $0 \le r < s$ nicht
\end{itemize}
ein solches $a$ kann uns versichern, dass $n$ zusammengesetzt ist, und heißt daher \emph{Zeuge gegen die Primalität von n}

\emph{Erklärungsversuch:}

Da der Fermat-Test z.B. bei den Carmichael-Zahlen versagt, macht sich der Miller-Rabin Test eine weitere Eigenschaft von
\((\mathbb{Z}/p\mathbb{Z})^*\) mit \(p\) prim zunutze.
\begin{equation}
   a^2 \equiv 1 \mod p \;\; \Longrightarrow a \equiv 1 \mod p \; \vee \; a \equiv -1 \mod p
   \label{quadratBedingung}
\end{equation}

Nur \(1 + p\mathbb{Z}\) und \(-1 + p\mathbb{Z}\) ergeben in dem Körper \(\mathbb{Z}/p\mathbb{Z}\) quadriert \(1 + p\mathbb{Z}\).
Siehe Übung v). Falls man also für eine Zahl \(n \in \mathbb{N}\) ein \(a + n\mathbb{Z} \) findet, sodass
\[
 a^2 \equiv 1 \mod n \;\; \wedge \;\; a \not\equiv 1 \mod n \;\; \wedge \;\; a \not\equiv -1 \mod n
\]
dann kann \(n\) keine Primzahl sein.

\emph{Beispiel:} Für \(n = 561\) ist \(67^2 \equiv 1 \mod 561\), damit kann 561 keine Primzahl sein.

Der Miller-Rabin Test kombiniert den Fermat-Test mit dieser Eigenschaft.

Testet man eine Zahl \(n\) mit dem Miller-Rabin Test gegen eine Zahl \(a\), definiert man dafür analog \buchmann{p. 129} erst zwei zusätzliche Werte $s$ und $d$ aus den obigen Formeln. \(d\) ist somit \(n-1\) geteilt durch die größtmögliche 2-er Potenz.\\
Der Sinn dahinter ist, dass man nun \(a^d\) so oft $\bmod n$ quadriert, bis wieder \(a^{n - 1}\) erreicht wird, und bei jeder Quadrierung
die obige Bedingung \ref{quadratBedingung} testet.
Ist diese nicht erfüllt (d.h. eine Zahl ist ungleich 1 bzw. -1 und ihr Quadrat mod \(n\) ergibt trotzdem 1), so war $\mathbb{Z}/n\mathbb{Z}$ kein Körper, $n$ keine Primzahl und das gewählte $a$ ein Zeuge gegen die Primalität von $n$.
\\

\begin{tabular}{|l|l|l|l|l|l||l|r|}
\hline
\textbf{r} & 0 & 1 & 2 & \dots & \(s - 1\) & \(s\) &  \\
\hline
\textbf{Quadrat} & \((a^{d})^{2^0} = a^d\) & \(((a^{d})^{2^0})^2 = (a^{d})^{2^1}\) & \(((a^{d})^{2^1})^2 = (a^{d})^{2^2}\) & \dots & \((a^{d})^{2^{s - 1}}\) & \( \overbrace{(a^{d})^{2^s} = a^{n - 1}}^{Fermat-Test} \) &  \\
\hline
\textbf{mod \(n\), Fall 1} & \textbf{1}\:[match!] & 1 & 1 & 1 & 1 & 1 & prim(?) \\
\hline
\textbf{mod \(n\), Fall 2} & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & \textbf{-1}\:[match!] & 1 & 1 & 1 & prim(?)\\
\hline
\textbf{mod \(n\), Fall 3} & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & \textbf{1}\:[match!] & 1 & 1 & 1 & zsg.(!) \\
\hline
\textbf{mod \(n\), Fall 4} & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & $\not\equiv \pm 1$  & $\not\equiv \pm 1$ & zsg.(!) \\
\hline
\end{tabular}

%(``?'' steht für \(\not= 1 \wedge \not= -1\))\\

\begin{itemize}
\item Bei \textbf{Fall 1} ist für \(r = 0\) \(a^d \equiv 1 \mod n\), damit ist auch klar, dass \(a^{n - 1} \equiv 1 \mod n\) gilt
und n \textbf{wahrscheinlich}
\footnote[1]{siehe Bemerkung zur Fehlerwahrscheinlichkeit}
prim ist.
\item Bei \textbf{Fall 2} ist eines der Quadrate \(\equiv -1 \mod n\) und damit alle folgenden Quadrate \(\equiv 1 \mod n\).
Damit ist \(n\) \textbf{wahrscheinlich}\footnotemark[1] prim.
\item Bei \textbf{Fall 3} ist \(n\) zusammengesetzt, also nicht prim, da eine Zahl \(\not= 1 \wedge \not= -1\) existiert,
deren Quadrat \(\equiv 1 \mod n\). Damit ist Bedingung \ref{quadratBedingung} verletzt.
\item Bei \textbf{Fall 4} ist \(n\) zusammengesetzt, also nicht prim, da \(a^{n-1} \not\equiv 1 \mod n\), sodass die Fermat-Bedingung fehl schlägt.
\end{itemize}

\emph{Hinweis:} Man muss nur bis \(r = s - 1\) testen, denn entweder
\begin{itemize}
 \item \((a^{d})^{2^{s - 1}} \equiv -1 \mod n\), damit ist \((a^{d})^{2^s} \equiv a^{n - 1} \equiv 1 \mod n\) und \(n\) ist \textbf{wahrscheinlich}\footnotemark[1] prim
 \item oder \((a^{d})^{2^{s - 1}} \not\equiv -1 \mod n\) und \(n\) ist zusammengesetzt, also nicht prim, weil entweder
 \begin{itemize}
  \item \((a^{d})^{2^s} \equiv a^{n - 1} \not\equiv 1 \mod n\), dann schlägt die Fermat-Bedingung fehl
  \item oder \((a^{d})^{2^s} \equiv a^{n - 1} \equiv 1 \mod n\), dann schlägt die Bedingung \ref{quadratBedingung} fehl\\
  (dann hätten wir eine Zahl gefunden, die ungleich 1 und -1 ist und deren Quadrat mod \(n\) trotzdem 1 ergibt.)
 \end{itemize}
\end{itemize}

\emph{Bemerkung zur Fehlerwahrscheinlichkeit:}

Im Positiv-Fall (Fall 3 und 4, es wurde mind. ein Zeuge gefunden), ist sichergestellt dass $n$ zusammengesetzt ist. 

Im Negativ-Fall (Fall 1 und 2, es konnte sich nach $k$-fachem Test unterschiedlicher $a$'s kein Zeuge für den Gegenbeweis finden lassen), muss $n$ \emph{in dubio pro reo} von seiner Nicht-Primalität freigesprochen werden, also mit einer gewissen Unsicherheit als prim entlassen werden. Diese Unsicherheit lässt sich in Zahlen ausdrücken, da man weiß wieviele Nicht-Zeugen es unter $n$ zur Auswahl stehenden Zeugen gibt. Es sind maximal $\frac{1}{4}(n-1)$ Stück. 

\emph{Beispiel:} $n$ gibt vor prim zu sein. Man unterzog $n$ eines Fermat-Schnelltests auf der Straße, konnte aber nicht belangt werden. Zweifelnde Beamte lassen nun aber nicht locker und nehmen $n$ mit auf die Wache, jedoch wird aus Zeitmangel nur genau 1 $a$ als Zeuge befragt - ohne Erfolg. $n$ wird also freigesprochen, ist aber trotzdem zusammengesetzt. Sauerei! Aber dann hat man eben in die maximal $25\%$ der unfähigen Zeugen gegriffen. Hätte man sich Zeit genommen und zur Sicherheit $k$ statt 1 Zeugen befragt, wäre die Trefferwahrscheinlichkeit auf einen falschen Zeugen auf $(0,25)^k$ gesunken.

\subsubsection{Verfahren in der Praxis \buchmann{8.3}}
Praxis-Algorithmus zur Bestimmung einer k-Bit Primzahl $n$ (mit bits $b_{k-1},...,b_1,b_0$):
\begin{itemize}
 \item setze $b_{k-1}$(sonst ist die Zahl nicht k-Bits lang) und $b_0$(damit die Zahl ungerade wird) auf 1
 \item wähle die restlichen 'mittleren' bits zufällig
 \item wende Probedivision für Primzahlen unterhalb einer Schranke B an. (damit der Aufwand vertretbar bleibt)
 \item wende Miller-Rabin-Test mit $k$ Wiederholungen auf $n$ an. Wird kein Zeuge gegen die Primalität gefunden gilt $n$ als prim.
\end{itemize}
Typischerweise wird $B=10^6$ gewählt, 
ebenfalls wird bei $n>2^{1000}$ mit $k=3$ schon eine Fehlerwahrscheinlichkeit $<\frac{1}{2}^{80}$ erreicht.







